home *** CD-ROM | disk | FTP | other *** search
/ AOL File Library: 2,801 to 2,900 / aol-file-protocol-4400-2801-to-2900.zip / AOLDLs / C++ Files Library / Linked List Template Classes / Linked Lists Ä.sit / Linked Lists ƒ / source code / LinkedLists.h < prev    next >
C/C++ Source or Header  |  1995-03-02  |  9KB  |  225 lines
  1. #pragma once
  2.  
  3.  
  4. /********************************************************************************************
  5.  
  6.     Class ListItem is used internally by the ListClasses; you don't have to worry about it.
  7.     It simply is a template class which will hold the class you're storing in the list and will
  8.     point to the next object in the list
  9.     
  10. ********************************************************************************************/
  11.  
  12. template <class itemClass> class ListItem {
  13.  
  14. public:
  15.     itemClass    item;
  16.     ListItem    *next;
  17. };
  18.  
  19.  
  20. /********************************************************************************************
  21.  
  22.     General List Info
  23.         Ñ "itemRecord" refers to the specific variable/class/struct type 
  24.           when an instance of this template class is created
  25.                         
  26. ********************************************************************************************/
  27.  
  28.  
  29. /********************************************************************************************
  30.  
  31.     SlimListClass
  32.             
  33.     SlimListClass is the most basic of all the Lists, providing simple Push and Pop operations.
  34.     (It will create a stack, with only the top item accessible, no sorting involved.)
  35.     
  36.     This class will also "clean up" after itself, deallocating all the memory it allocates when
  37.     it is terminated.
  38.  
  39.  
  40.     Function Usage
  41.     
  42.     var.Push(itemRecord theItem);
  43.         Ñ will "push" the item on to the top of the stack
  44.         Ñ returns 1 if successful, 0 if not (memory couldn't be allocated)
  45.     
  46.     item=var.Pop();
  47.         Ñ "pops" the top item - takes it off the stack and returns item
  48.         
  49.     var.DeleteAll();
  50.         Ñ deletes all entries in stack
  51.         Ñ also called when variable is destroyed (e.g., local variable in function dieing when
  52.           function is done)
  53.     
  54.  
  55. ********************************************************************************************/
  56.     
  57.  
  58. template <class itemRecord> class SlimListClass {
  59. protected:
  60.     ListItem<itemRecord>    *theList;
  61. public:
  62.     SlimListClass()        { theList=theList->next=nil; }
  63.     ~SlimListClass()    { DeleteAll(); }
  64.     Boolean        Push(itemRecord &theItem);
  65.     itemRecord    Pop();
  66.     void        DeleteAll(); 
  67. };
  68.  
  69.  
  70.  
  71.  
  72.  
  73. /********************************************************************************************
  74.  
  75.     SlimPlusClass
  76.  
  77.     SlimPlusClass is essentially the same as its base class, SlimListClass, but with a query
  78.     function, as well as a useful function, "XInList", explained below.  Because of the
  79.     latter function, this class needs two object types when creating it.  The reason will 
  80.     become clear with the explanation of "XInList".
  81.     
  82.     Special Note:
  83.         Because this class compares the objects you specify when creating it (the itemRecord
  84.         objects) you must provide for object comparison in your object class (with ==, only).
  85.         
  86.             example
  87.                  class declaration {
  88.                 // var declarations in class
  89.                 // function declarations in class
  90.                 Boolean operator == (myClass rightObject) { return *this==rightObject; }
  91.                 };
  92.                 
  93.                 (you can compare whatever feature of the objects with each other as is necessary)
  94.                 
  95.     
  96.     Function Usage
  97.     
  98.     var.ItemInList(theItem)
  99.         Ñ is passed an item, of type itemRecord, returns if item is in list (1 or 0)
  100.         
  101.     var.XInList(thisComparisonObject, * &theItem)
  102.         Ñ passed an object to compare theItem with, XInList will return if item is in list
  103.         Ñ if the comparison object is in the list, theItem parameter will be set to a pointer to
  104.           that object
  105.         Ñ examples/suggestions for usage:
  106.         
  107.             I create my own dialog and window classes, and throw them into a linked list.  When I
  108.             receive update/activate/etc. events, I pass the WindowPtr in the first parameter and
  109.             a dialog/window class pointer in the second parameter.  The SlimPlusClass will then
  110.             compare these two with each item in the list, returning the first match it finds in
  111.             the second paramater, or 0 if it's not found.  If it finds a match, I simply call the 
  112.             update procedure in the returned object.
  113.             
  114.             Important note: You must have a logic comparison in the itemRecord class for the 
  115.             comparison class.  For example, suppose you create SlimPlusList<myWindowClass, WindowPtr>.
  116.             Within myWindowClass, you must overload the "==" operator for myWindowClass==WindowPtr
  117.             logic tests.
  118.             
  119.         Ñ a pointer is returned so that changes will be made to _that_ object; if you simply used
  120.           a reference variable of the object, a copy of that object would be made so changes to
  121.           the object returned would not be made to the object in the list
  122.  
  123. ********************************************************************************************/
  124.     
  125. template <class itemRecord, class comparisonObject> class SlimPlusClass : public SlimListClass<itemRecord> {
  126.  
  127. public:
  128.     Boolean    ItemInList(itemRecord &theItem);
  129.     Boolean    XInList(comparisonObject theObject, itemRecord * &theItem);
  130. };
  131.  
  132.  
  133.  
  134.  
  135.  
  136. /********************************************************************************************
  137.  
  138.     ListClass
  139.     
  140.     ListClass is a the most featured list here, capable of sorting entries as they're input,
  141.     retrieving any object from the list, and providing information on the number of items
  142.     in the list.  ListClass also has a placeholder, pointing to the current place in the list.
  143.     Its significance is discussed below.
  144.     
  145.     Funcation Usage
  146.     
  147.     Push, Pop, and DeleteAll are all the same as the SlimListClass defined above.
  148.     
  149.     var.NumItems()
  150.         Ñ returns the number of items in the list
  151.     
  152.     var.Add(theItem)
  153.         Ñ instead of pushing the item on the stack, Add adds the item to the end of the list
  154.     
  155.     var.AddSort(theItem)
  156.         Ñ AddSort will sort the input as it's entered, provided you've defined (overloaded) all
  157.           the logical operators for your class ( <, >, ==, != )
  158.         Ñ Using AddSort to enter all items will create an ascending list (lesser objects at
  159.           the stack top, down to the greater items)
  160.           
  161.         Ñ Important note: AddSort will sort only the piece that's entered, not the whole list.
  162.           That is, if you Push some items on, Add others, then AddSort an item, the list will
  163.           not be sorted, and the item will be placed after the first object it's greater than
  164.     
  165.     var.Delete(theItem)
  166.         Ñ Given an item, it will purge the item, and the memory the item occupied, from the list
  167.         
  168.     var.SetToTop()
  169.         Ñ This sets the placeholder to the top item
  170.         Ñ Returns 1 if there is a stack top (there is a list), 0 otherwise
  171.     
  172.     var.GetPlaceItem(* &theItem)
  173.         Ñ This returns a pointer to the itemRecord object currently pointed to in the list in
  174.           second parameter
  175.         Ñ Returns a non-zero value if there is an item there
  176.     
  177.     var.GetNextItem(* &theItem)
  178.         Ñ Returns a pointer to the next itemRecord object in the list in second parameter
  179.         Ñ Returns a non-zero value if there is a "next" object
  180.         Ñ Sets the placeholder to the next item
  181.         
  182.     var.GetItemX(itemNumber, * &theItem)
  183.         Ñ Returns a pointer to the xth item (first, second, etc.) in a list in second parameter
  184.         Ñ Returns 1 if there is an item x, 0 if not
  185.         
  186.     Suggestions for using placeholder-related functions
  187.         I use this list class for data which should be sorted as well as for data which shouldn't be.
  188.  
  189.         A good example of the former use is when you have to find the median (middle number) in a set
  190.         of inputted data.  As the user inputs the data, I AddSort() it to a list.  When I need to
  191.         report back the median, I query the number of items in the list with NumItems(), then use 
  192.         this number to GetItemX().  
  193.         
  194.         When the order of the data entered should be preserved, I simply use Add() which will keep
  195.         the first item entered at the top of the list.  Then, when I need to retrieve each item of
  196.         the list, I SetToTop() which sets the placeholder to the top of the list, GetPlaceItem(),
  197.         which retrieves the top item if it's there, then do a simple while loop that goes until
  198.         GetNextItem returns 0 (actually nil), retrieving each successive item in the list.
  199.  
  200. ********************************************************************************************/
  201.  
  202.     
  203. template <class itemRecord> class ListClass {
  204.  
  205. protected:
  206.     ListItem<itemRecord>    *stackTop;
  207.     ListItem<itemRecord>    *placeHolder;
  208.     int    numberOfItems;
  209. public:
  210.     ListClass() { placeHolder=stackTop=nil; numberOfItems=0; }
  211.     ~ListClass() { DeleteAll(); }
  212.     int        NumItems() { return numberOfItems; }
  213.     Boolean    AddSort(itemRecord &theItem);
  214.     Boolean    Add(itemRecord &theItem);
  215.     Boolean    Push(itemRecord &theItem);
  216.     itemRecord    Pop();
  217.     void    Delete(itemRecord theItem);
  218.     void    DeleteAll();
  219.     Boolean    SetToTop() { placeHolder=stackTop; if (stackTop) return 1; return 0;}
  220.     ListItem<itemRecord>    *GetPlaceItem(itemRecord * &theItem);
  221.     ListItem<itemRecord>    *GetNextItem(itemRecord * &theItem);
  222.     Boolean    GetItemX(short itemNumber, itemRecord * &theItem);
  223. };
  224.  
  225.